#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet; /* 默认元素为整数*/
#define Swap(x, y) { ElemSet t = x; x = y; y = t; }

/* 插入排序 */
void InsertionSort(ElemSet *a, int l, int r) {
    ElemSet t;
    int i, j;

    for (i = l + 1; i <= r; i++) {
        t = a[i];
        for (j = i; j >= (l + 1); j--) {
            if (a[j - 1] > t) {
                a[j] = a[j - 1];
            } else {
                break;
            }
        }
        a[j] = t;
    }
}
/* 插入排序结束 */

/* 堆的定义与操作 */
typedef ElemSet HElemSet;
typedef int Position; /* 数组下标即为元素位置 */
typedef struct BinaryHeapNode *MaxHeap;
struct BinaryHeapNode {
    HElemSet *data; /* 数据元素数组 */
    int size; /* 规模 */
    int capacity; /* 容量 */
};

void SiftDown(MaxHeap h, Position i) {
    Position last, child;
    HElemSet elem;

    last = h->size - 1; /* 这是最后一个元素的位置 */
    elem = h->data[i];
    while (1) {
        child = (i << 1) + 1; /* child当前是i的左孩子的位置 */
        if (child < last
                && h->data[child + 1] > h->data[child]) { /* 如果i有右孩子并且右孩子更大 */
            child++; /* child更新为i的右孩子的位置 */
        } else if (child > last) { /* 如果i是叶子结点 */
            break; /* 已经调整到底，跳出循环 */
        }
        if (elem < h->data[child]) { /* 若较大的孩子比elem大 */
            h->data[i] = h->data[child]; /* 将较大的孩子结点上移 */
            i = child; /* i指向原结点的孩子结点，即向下调整 */
        } else { /* 若所有孩子都不比elem大 */
            break; /* 则找到了elem的最终位置，跳出循环 */
        }
    }
    h->data[i] = elem;
}

void MakeHeapDown(MaxHeap h) {
    Position last;
    int i;

    last = h->size - 1; /* 这是最后一个元素的位置 */
    for (i = (last - 1) >> 1; i >= 0; i--) {
        SiftDown(h, i); /* 自底向上调整 */
    }
}
/* 堆的定义与操作结束 */

/* 堆排序 */
void HeapSort(ElemSet *a, int l, int r) {
    MaxHeap h;

    h = (MaxHeap)malloc(sizeof(struct BinaryHeapNode));
    h->capacity = h->size = r - l + 1;
    h->data = a + l;
    MakeHeapDown(h); /* 建最大堆 */
    while (h->size > 1) { /* 基于堆的排序 */
        Swap(h->data[0], h->data[h->size - 1]);
        h->size--;
        SiftDown(h, 0);
    }
    free(h);
}
/* 堆排序结束 */

int Partition(ElemSet *a, int l, int r) {
    int i, j;
    ElemSet p;

    i = l;
    j = r - 1;
    p = a[r]; /* 选择序列最后一个元素作为轴点 */
    while (1) {
        while (a[i] < p) { /* 找到i以右第一个大于等于轴点的元素 */
            i++;
        }
        while (a[j] > p
                && j > l) { /* 找到j以前第一个小于等于轴点的元素 */
            j--;
        }
        if (i >= j) { /* 如果i大于等于j，完成拆分，退出循环 */
            break;
        }
        Swap(a[i], a[j]); /* 交换a[i]和a[j]并右移i左移j */
        i++;
        j--;
    }
    Swap(a[i], a[r]); /* 此时{a[l], ..., a[i-1]}<=a[i]<={a[i+1], ..., a[r]}*/
    return i;
}

#define kThrLen 3
/* 算法10-21：内省排序 IntroSort(a,l,r,d) */
void IntroSort(ElemSet *a, int l, int r, int d) {
    int i;

    if ((r - l) < kThrLen) { /* 若小于短子序列的阈值 */
        InsertionSort(a, l, r);
    } else if (d == 0) {
        HeapSort(a, l, r);
    } else {
        i = Partition(a, l, r);
        IntroSort(a, l, i - 1, d - 1);
        IntroSort(a, i + 1, r, d - 1);
    }
}
/* 算法10-21 结束 */

#define kThrD 2
int main(void) {
    ElemSet *a; /* 数组a的下标从0开始 */
    int n, i;

    scanf("%d", &n);
    a = (ElemSet *)malloc(sizeof(ElemSet) * n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    IntroSort(a, 0, n - 1, kThrD);
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }

    return 0;
}